/*
 * Компоненты связности
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <assert.h>

/* {{{ autoarray */
struct vector {
	int *data;
	int n;
	int max;
};

void
vector_init(struct vector *v, int p)
{
	if (p < 0)
		p = 0;
	v->max = 1 << p;
	v->n = 0;
	v->data = (int *) calloc((size_t) v->max, sizeof *v->data);
}

int
vector_append(struct vector *v, int a)
{
	int *t;

	if (v->max == 0)
		vector_init(v, 0);

	if (v->n + 1 > v->max) {
		t = (int *) realloc(v->data, sizeof *t * (v->max *= 2));
		if (!t) {
			fprintf(stderr, "vector_append(): failed to allocate %d bytes\n", v->max);
			return 1;
		} else {
			v->data = t;
		}
	}

	v->data[v->n++] = a;

	return 0;
}

int
vector_sort(struct vector *v, int (*cmpf)(const void *, const void *))
{
	if (v->max > 0 && v->n > 1) {
		qsort(v->data, (size_t) v->n, sizeof *v->data, cmpf);
		return 0;
	} else {
		return 1;
	}
}

int
vector_cleanup(struct vector *v)
{
	if (v->max > 0) {
		v->max = v->n = 0;
		free(v->data);
		v->data = NULL;
		return 0;
	} else {
		return 1;
	}
}
/* }}} */

/* {{{ adjlist w/ vector */
struct adjlist {
	struct vector adj_v;
	bool visited;
	unsigned short csid;
};

void
adjl_connect(struct adjlist *node, int conid)
{
#ifdef D2_FPARAM
	fprintf(stderr, "adjl_connect(node=%p = { adj_v = { data=%p, n=%d, max=%d } , s=%d}, conid=%d)\n",
			node, node->adj_v.data, node->adj_v.n, node->adj_v.max, node->s, conid);
#endif
	if (node->adj_v.max == 0)
		vector_init(&node->adj_v, 1);
	vector_append(&node->adj_v, conid);
}

void
adjl_cleanup(struct adjlist *node)
{
	vector_cleanup(&node->adj_v);
}
/* }}} */

int
dfs_mark_connection_spaces(struct adjlist * const al, const int node_idx, const unsigned short csid)
{
	int i = 0;

	al[node_idx].visited = true;
	al[node_idx].csid = csid;
	while (i < al[node_idx].adj_v.n) {
		/* long unreadable variable names always help */
		if (al[ al[node_idx].adj_v.data[i] ].visited == false) {
			dfs_mark_connection_spaces(al, al[node_idx].adj_v.data[i], csid);
		} else {
			assert(al[ al[node_idx].adj_v.data[i] ].csid == csid);
		}
		i++;
	}
	return 0;
}

int
main(int argc, char **argv)
{
	struct adjlist *al;
	int i, n, m;
	int a, b;
	unsigned short csid = 1U; /* connection space ID */

	scanf("%d%d", &n, &m);
	al = (adjlist *) calloc((size_t) n, sizeof *al);
	for (i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		--a; --b;
		adjl_connect(al + a, b);
		adjl_connect(al + b, a);
	}

	for (i = 0; i < n; i++) {
		if (al[i].visited == false) {
			dfs_mark_connection_spaces(al, i, csid++);
		}
	}

	printf("%d\n", csid - 1);
	for (i = 0; i < n; i++) {
		printf("%hu%c", al[i].csid, (i + 1 == n) ? '\n' : ' ');
		adjl_cleanup(al + i);
	}

	free(al);
	return 0;
}
